﻿#define _CRT_SECURE_NO_WARNINGS


//#include<iostream>
//using namespace std;
//const int N = 10010;
//int g[N];
//int w[N], v[N];
//int n,V;
//int main()
//{
//	cin >> n>>V;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> v[i] >> w[i];
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = v[i]; j<=V; j++)
//		{
//			g[j] = max(g[j], g[j - v[i]] + w[i]);
//		}
//	}
//	cout << g[V];
//
//	return 0;
//}



//#include<iostream>
//using namespace std;
//const int N = 10010;
//int n, V;
//int w[N], v[N],s[N];
//int f[N][N];
//int  main()
//{
//	cin >> n >> V;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> v[i] >> w[i] >> s[i];
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = v[i]; j <= V; j++)
//		{
//			for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
//			{
//				f[i][j] = max(f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i]);
//			}
//		}
//	}
//	cout << f[n][V];
//	return 0;
//}




//#include<iostream>
//using namespace std;
//const int N = 10010;
//int g[N];
//int n, m;
//int w[N],v[N];
//int main()
//{
//	cin >> n >> m;
//	int cnt = 0;
//	while (n--)
//	{
//		int a, b, c;
//		cin >> a >> b >> c;
//		for (int i = 1; i <= c; i*=2)
//		{
//			cnt++;
//			w[cnt] = i * b;
//			v[cnt] = a * i;
//			c -= i;
//		}
//		if (c != 0)
//		{
//			cnt++;
//			w[cnt] = c * b;
//			v[cnt] = c * a;
//		}
//	}
//	n = cnt;
//	for (int i = 1; i <= cnt; i++)
//	{
//		for (int j = m; j >= v[i]; j--)
//		{
//			g[j] = max(g[j], g[j - v[i]] + w[i]);
//		}
//	}
//	cout << g[m];
//	return 0;
//}




//#include<iostream>
//using namespace std;
//const int N = 1010;
//int n;
//int num[N][N];
//int f[N][N];
//int main()
//{
//	cin >> n;
//	memset(f,-0x3f, sizeof(f));
//	f[0][0] = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cin >> num[i][j];
//			f[i][j] = 0;
//		}
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + num[i][j];
//		}
//	}
//	/*int max = -1e9;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cout << f[i][j] << ' ';
//		}
//		cout << endl;
//	}*/
//	int max = -1e9;
//	for (int i = 1; i <= n; i++)
//	{
//		if (max < f[n][i])
//		{
//			max = f[n][i];
//		}
//	}
//	cout << max;
//
//	return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 100010;
//int f[N];
//int n;
//int num[N];
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> num[i];
//	}
//	int res = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <i; j++)
//		{
//			if (num[i] >= num[j])
//			{
//				f[i] =max(f[i], f[j] + 1);
//			}
//			if (f[i] > res)
//			{
//				res = f[i];
//			}
//		}
//	}
//	/*for (int i = 1; i <= n; i++)
//	{
//		cout << f[i] << ' ';
//	}*/
//	cout << res + 1;
//	return 0;
//}




//#include<iostream>
//using namespace std;
//int num[10010];
//int main()
//{
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	int end = 0;
//	int gap = 3;
//	int tmp = num[end + gap];
//	while (end >= 0)
//	{
//		if (tmp < num[end])
//		{
//			num[end + gap] = num[gap];
//
//		}
//	}
//	return 0;
//}


//#include<stdio.h>
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int t = 0;
//    while (a % 2 == 0 && b % 2 == 0)
//    {
//        a /= 2;
//        b /= 2;
//    }
//    while (t != a)
//    {
//        if (a < b)
//        {
//            int p = a;
//            a = b;
//            b = p;  //t2=b-t 
//        }          //t=a-b b-t
//        t = a - b;//2=3-1   t=1  a=3   b=2  
//        a = b;//a=b a=2 
//        b = t;//b=t b=1;
//    }
//    printf("%d", b);
//    return 0;
//}




//#include<iostream>
//using namespace std;
//int n;
//int num[10010];
//int main()
//{
//	std::ios::sync_with_stdio(false);
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	int gap = 3;
//
//	return 0;
//}




//#include<iostream>
//using namespace std;
//int main()
//{
//	int num[100010];
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	int gap = n;
//	while (gap > 1)
//	{
//		gap =gap/3+1;
//		for (int i = 0; i < n-gap; i+=gap)
//		{
//			int end = i;
//			int tmp = num[i + gap];
//			while (end >= 0)
//			{
//				if(num[end]>tmp)
//				{
//					num[end + gap] = num[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}	
//			}
//			num[end+gap] = tmp;
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}



//#include<iostream>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//
//
//	return 0;
//}




//#include<iostream>
//using namespace std;
//int n;
//int num[10010];
//bool st[10010];
//void bfs(int u)
//{
//	if (u == n)
//	{
//		for (int i = 0; i < n; i++)
//		{
//			cout << num[i] << ' ';
//		}
//		cout << endl;
//		return;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		if (!st[i])
//		{
//			num[u] = i;
//			st[i] = true;
//			bfs(u + 1);
//			st[i] = false;
//		}
//	}
//}
//int main()
//{
//	cin >> n;
//	bfs(0);
//	return 0;
//}


//#include<iostream>
//#include<queue>
//using namespace std;
//typedef pair<int, int>PII;
//queue<PII>q;
//int n, m;
//int num[1010][1010];
//int d[1010][1010];
//int dx[4] = { 0,1,0,-1 };
//int dy[4] = { 1,0,-1,0 };
//int main()
//{
//	cin >> n >> m;
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			cin >> num[i][j];
//		}
//	}
//	q.push({0,0});
//	while (q.size())
//	{
//		auto t = q.front();
//		q.pop();
//		for (int i = 0; i < 4; i++)
//		{
//			int x = t.first + dx[i];
//			int y = t.second + dy[i];
//			if (x >= 0 && x < n && y >= 0 && y < m&& num[x][y] == 0)
//			{
//				d[x][y] = d[t.first][t.second] + 1;
//				q.push({x, y});
//			}
//		}
//	}
//	cout << d[n - 1][m - 1];
//	return 0;
//}




//#include<iostream>
//using namespace std;
//void quick_sort(int* a, int l, int r)
//{
//
//}
//int main()
//{
//
//
//
//
//	return 0;
//}



//#include<iostream>
//using namespace std;
//int num[1000010];
//void quick_sort(int num[], int l, int r)
//{
//	if (l >= r)return;
//	
//}
//int main()
//{
//	std::ios::sync_with_stdio(false);
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	quick_sort(num, 0, n - 1);
//	return 0;
//}




//#include<iostream>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	int target = 0;
//	cin >> target;
//	int l = 0; int r = n - 1;
//	int mid = 0;
//	while (l <= r)
//	{
//		mid = l + r >> 1;
//		if (num[mid] > target)
//		{
//			l = mid + 1;
//		}
//		else if(num[mid]<target)
//		{
//			r = mid - 1;
//		}
//		else if (num[mid] == target)
//		{
//			cout << mid << endl;
//			return 0;
//		}
//	}
//	return 0;
//}



//#include<iostream>
//using namespace std;
//int num[10010];
//int main()
//{
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	int i = 0;
//	int j = 0;
//	for (i = 0; i < n; i++)
//	{
//		for (j = i - 1; j >= 0; j--)
//		{
//			if (num[i] > num[j])
//			{
//				break;
//			}
//		}
//		int tmp = num[i];
//		if (j != i - 1)
//		{
//			for (int k = i; k >j; k--)
//			{
//				num[k] = num[k-1];
//			}
//			num[j + 1] = tmp;
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}



//#include<iostream>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	for (int i = 0; i < n; i++)
//	{
//		cin >> num[i];
//	}
//	int gap = n;
//	int i = 0;
//	int j = 0;
//	while (gap>1)
//	{
//		gap /= 2;
//		for (i = gap; i <=n-gap; i += gap)
//		{
//			for (j = i - gap; j >= 0; j-=gap)
//			{
//				if (num[j] > num[i])
//				{
//					break;
//				}
//			}
//			int tmp = num[i];
//			for (int k = i; k > j; k -= gap)
//			{
//				num[k] = num[k - gap];
//			}
//			num[j + gap] = tmp;
//		}
//	}
//	for (int l = 0; l < n; l++)
//	{
//		cout << num[l] << ' ';
//	}
//
//	return 0;
//}




//#include<iostream>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	for (int i = 0; i < n; i++)
//		cin >> num[i];
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < i - 1; j++)
//		{
//			if (num[j] > num[j + 1])
//			{
//				int t = num[j];
//				num[j] = num[j + 1];
//				num[j + 1] = t;
//			}
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}


//#include<iostream>
//int a = 0;
//#define cout std::cout
//int main()
//{
//	int t=0;
//	cout << t;
//
//
//	return 0;
//}




//#define _CRT_SECURE_NO_WARNINGS 1
//#include "game.h"
//void menu()
//{
//	printf("******************************\n");
//	printf("*******  1.play   ************\n");
//	printf("*******   0.exit    **********\n");
//}
//void game()
//{
//	//存储数据-二维数组
//	char board[ROW][COL];
//
//	//初始化棋盘-初始化空格
//	InitBoard(board, ROW, COL);//如果不初始化，打印的很丑，都是问号
//
//	//打印一下棋盘--本质是打印数组的内容
//	DisplayBoard(board, ROW, COL);
//
//
//}
//int main()
//{
//	int input = 0;
//	do
//	{
//		menu();
//		printf("请选择:>");
//		scanf("%d", &input);
//		switch (input)
//		{
//		case 1:
//			game();
//			break;
//		case 0:
//			printf("退出游戏\n");
//			break;
//		default:
//			printf("选择错误，重新选择\n");
//			break;
//		}
//	} while (input);
//	return 0;
//}


//#include<iostream>
//namespace bit {
//	int a = 0;
//}
////using namespace bit;
//int main()
//{
//	std::cout << bit::a;
//
//	return 0;
//}


//#include<algorithm>
//#include<iostream>
//#include<time.h>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	srand(time(NULL));
//	for (int i = 0; i < n; i++)
//	{
//		int x = (int)rand() % 1000;
//		num[i] = x;
//	}
//	sort(num, num + n);
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	cout << endl;
//	int i = 0;
//	int j = 0;
//
//	for (i = 0; i < n; i++)
//	{
//		for (j = i - 1; j >= 0; j--)
//		{
//			if (num[i] > num[j])
//			{
//				break;
//			}
//		}
//		int tmp = num[i];
//		for (int k = i; k >j&&k>0; k--)
//		{
//			num[k] = num[k-1];
//		}
//		num[j+1] = tmp;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}



//#include<time.h>
//#include<algorithm>
//#include <iostream>
//using namespace std;
//bool cmp(int a, int b)
//{
//	return a < b;
//}
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	int b2[10010];
//	srand(time(NULL));
//	for (int i = 0; i < n; i++)
//	{
//		int x = rand();
//		num[i] = x;
//		b2[i] = x;
//	}
//	sort(b2, b2 + n,cmp);
//	for (int i = 0; i < n; i++)
//	{
//		cout << b2[i] << ' ';
//	}
//	cout << endl;
//	int gap = n;
//	int i = 0;
//	int j = 0;
//	while (gap > 1)
//	{
//		gap /= 2;
//		for (i = gap; i <= n - gap; i += gap)
//		{
//			for (j = i - gap; j >=0; j-=gap)
//			{
//				if (num[i] >num[j])
//				{
//					break;
//				}
//			}
//			int tmp = num[i];
//			for (int k = i; k >j; k -= gap)
//			{
//				num[k] = num[k - gap];
//			}
//			num[j+gap] = tmp;
//		}
//	}
//	for (i = 0; i < n; i++)
//	{
//		if (num[i] != b2[i])
//		{
//			cout << "NO" << endl;
//			return 0;
//		}
//	}
//	cout << "YES\n";
//	return 0;
//}


//#include<time.h>
//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	//int num[10010];
//	priority_queue<int,vector<int>, greater<int>>h;
//	for (int i = 0; i < n; i++)
//	{
//		h.push(rand() % 1000);
//	}
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d\n", h.top());
//		h.pop();
//	}
//	return 0;
//}


                                 ////快排
//#include<iostream>
//#include<time.h>
//#include<algorithm>
//using namespace std;
//void quick_sort(int num[], int l, int r)//快速的排序
//{
//	if (l >= r)	return;
//	int mid = l + r >> 1;
//	int i = l - 1;
//	int j = r + 1;
//	while (i < j)
//	{
//		do {
//			i++;
//		} while (num[mid] > num[i]);
//		do {
//			j--;
//		} while (num[mid] < num[j]);
//		if (i < j)
//		{
//			swap(num[i], num[j]);
//		}
//	}
//	quick_sort(num, l, j);
//	quick_sort(num, j+1, r);
//}
//int main()
//{
//	int n;
//	cin >> n;
//	int num[10010];
//	srand(time(NULL));
//	for (int i = 0; i < n; i++)
//	{
//		int x = rand() % 1000;
//		num[i] = x;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	cout << endl;
//	sort(num,num+n);
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	cout << endl;
//	quick_sort(num, 0, n-1);
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}


//#include<time.h>
//#include<vector>
//#include<algorithm>
//#include<iostream>
//using namespace std;
//int main()
//{
//	srand(time(NULL));
//	vector<int>q;
//	vector<int>w;
//	vector<int>p;
//	vector<int>l;
//	int n,m;
//	cin >> n>>m;
//	for (int i = 0; i < n; i++)
//	{
//		int t = rand() % 10010;
//		q.push_back(t);
//		l.push_back(t);
//	}
//	for (int i = 0; i < m; i++)
//	{
//		int t = rand() % 10010;
//		p.push_back(t);
//		l.push_back(t);
//	}
//	sort(q.begin(), q.end());
//	sort(p.begin(), p.end());
//	sort(l.begin(), l.end());
//	for (auto p : l)
//	{
//		cout << p<<' ';
//	}
//	cout << endl;
//	int t = n + m;
//	if (t % 2 == 1)
//	{
//		t /= 2;
//		int i = 0;
//		int j = 0;
//		while (i < q.size() && j < p.size())
//		{
//			while (i < q.size() && j < p.size() && q[i] < p[j])
//			{
//				w.push_back(q[i]);
//				i++;
//			}
//			while (j < p.size() && i < q.size() && q[i] >= p[j])
//			{
//				w.push_back(p[j]);
//				j++;
//			}
//		}
//		while (i < q.size())
//		{
//			w.push_back(q[i]);
//			i++;
//		}
//		while (j < p.size())
//		{
//			w.push_back(p[j]);
//			j++;
//		}
//		double sum=0.0;
//		sum += w[t]*1.0;
//		printf("%lf", sum);
//	}
//	else
//	{
//		t /= 2;
//		int i = 0;
//		int j = 0;
//		int sum = 0;
//		int o = 0;
//		while (i < q.size() && j < p.size())
//		{
//			while (i < q.size()&& j < p.size()&&q[i] < p[j])
//			{
//				w.push_back(q[i]);
//				i++;
//			}
//			while (j<p.size()&&i<q.size()&&q[i] >= p[j] )
//			{
//				w.push_back(p[j]);
//				j++;
//			}
//		}
//		while (i < q.size())
//		{
//			w.push_back(q[i]);
//			i++;
//		}
//		while (j < p.size())
//		{
//			w.push_back(p[j]);
//			j++;
//		}
//		sum += w[t] += w[t - 1];
//		double h = (sum * 1.0) / 2;
//		printf("%lf", h);
//	}
//	return 0;
//}


//#include<iostream>
//using namespace std;
//void fun(int a,int b=10)
//{
//	cout << a << ' ' << b;
//}
//int main()
//{
//	int a = 20;
//	fun(a);
//	return 0;
//}



//#include<stdio.h>
//int main()
//{
//	double b;
//	int n;
//	scanf("%d",&n);
//	if (n <= 10000)
//	{
//		b = n * 0.05 + 1500.00;
//	}
//	else if (n > 10000 && n <= 500000)
//	{
//		b = (n - 10000) * 0.03 + 1500.00 + 10000 * 0.05;
//	}
//	else
//	{
//		printf("%.2f", (n - 50000) * 0.020000 + 1500.00 + 10000.00 * 0.0500000 + 40000.00 * 0.030000);
//		return 0;
//		//b = (n - 50000) * 0.020000 + 1500.00 + 10000.00 * 0.0500000+40000.00*0.030000;
//	}
//	printf("%.2lf", b);
//	return 0;
//}


//#include<algorithm>
//#include<time.h>
//#include<iostream>
//using namespace std;
//int tmp[100010];
//int num[10010];
//int b[10010];
//void merge_sort(int l,int r)
//{
//	if (l >= r)return;
//	int mid = l + r >> 1;
//	merge_sort(l, mid);
//	merge_sort(mid + 1, r);
//	int k = 0, i = l, j = mid + 1;
//	while (i<=mid&&j<=r)
//	{
//		if (num[i] < num[j])
//		{
//			tmp[k++] = num[i++];
//		}
//		if (num[i] >= num[j])
//		{
//			tmp[k++] = num[j++]; 
//		}
//	}
//	while (j <= r)
//	{
//		tmp[k++] = num[j++];
//	}
//	while (i <= mid)
//	{
//		tmp[k++] = num[i++];
//	}
//	for (i = l, j = 0; i <= r; i++,j++)
//	{
//		num[i] = tmp[j];
//	}
//}
//int main()
//{
//	int n;
//	cin >> n;
//	srand(time(NULL));
//	for (int i = 0; i < n; i++)
//	{
//		int x;
//		x = rand() % 1000;
//		num[i] = x;
//		b[i] = x;
//	}
//	sort(b, b + n);
//	for (int i = 0; i < n; i++)
//	{
//		cout << b[i] << ' ';
//	}
//	cout << endl;
//	merge_sort(0,n-1);
//	for (int i = 0; i < n; i++)
//	{
//		cout << tmp[i] << ' ';
//	}
//	return 0;
//}



////选择排序
//#include<algorithm>
//#include<time.h>
//#include<iostream>
//using namespace std;
//int num[100010];
//int n;
//int b[100010];
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		int x = rand() % 10010;
//		num[i] = x;
//		b[i] = x;
//	}
//	sort(b, b + n);
//	for (int i = 0; i < n; i++)
//	{
//		cout << b[i] << ' ';
//	}
//	cout << endl;
//	int mini = 0;
//	int tmp[10010];
//	int j = 0;
//	for (int i = 0; i < n; i++)
//	{
//		mini = i;
//		for (j = i+1; j < n; j++)
//		{
//			if (num[mini] > num[j])
//			{
//				mini = j;
//			}
//		}
//		swap(num[mini], num[i]);
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}


//#include<time.h>
//#include<algorithm>
//#include<iostream>
//using namespace std;
//int num[100010];
//int b[10010];
//int n;
//void quick_sort(int l, int r)
//{
//	if (l >= r) return;
//	int mid = l + r >> 1;
//	int i = l - 1;
//	int j = n + 1;
//	while (i < j)
//	{
//		do 
//		{
//			i++;
//		} while (num[mid] > num[i]);
//		do 
//		{
//			j--;
//		} while (num[mid] < num[j]);
//		if (i < j)
//		{
//			swap(num[i], num[j]);
//		}
//	}
//	quick_sort(l, i);
//	quick_sort(j+1, r);
//}
//int main()
//{
//	cin >> n;
//	srand(time(NULL));
//	for (int i = 0; i < n; i++)
//	{
//		int x = rand() % 10010;
//		num[i] = b[i] = x;
//	}
//	sort(b, b + n);
//	n=union(b, b + n)-b;
//	for (int i = 0; i < n; i++)
//	{
//		cout << b[i] << ' ';
//	}
//	cout << endl;
//	quick_sort(0, n - 1);
//	for (int i = 0; i < n; i++)
//	{
//		cout << num[i] << ' ';
//	}
//	return 0;
//}



//#include<iostream>
//#include<algorithm>
//#include<time.h>
//using namespace std;
//int num[10010];
//int n;
//int b[10010];
//
//int main()
//{
//    cin >> n;
//    srand(time(NULL));
//    for (int i = 0; i < n; i++)
//    {
//        int x = rand() % 10010;
//        num[i] = x;
//        b[i] = x;
//    }
//    sort(b, b + n);
//    for (int i = 0; i < n; i++)
//    {
//        cout << b[i] << ' ';
//    }
//    cout << endl;
//    int mini = 0;
//    for (int i = 0; i < n; i++)
//    {
//        mini = i;
//        for (int j = i + 1; j < n; j++)
//        {
//            if (num[mini] > num[j])
//            {
//                mini = j;
//            }
//        }
//        swap(num[mini], num[i]);
//    }
//    for (int i = 0; i < n; i++)
//    {
//        cout << num[i] << ' ';
//    }
//    return 0;
//}


//#include<iostream>
//#include<algorithm>
//#include<time.h>
//using namespace std;
//int num[10010];
//int n;
//int b[10010];
//void bubble()
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = i; j <n-1-i; j++)
//        {
//            if (num[j] > num[j + 1])
//            {
//                swap(num[j],num[j + 1]);
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> n;
//    srand(time(NULL));
//    for (int i = 0; i < n; i++)
//    {
//        int x = rand() % 10010;
//        num[i] = x;
//        b[i] = x;
//    }
//    sort(b, b + n);
//    for (int i = 0;  i < n; i++)
//    {
//        cout << b[i] << ' ';
//    }
//    cout << endl;
//    for (int i = 0; i < n; i++)
//    {
//        cout << num[i] << ' ';
//    }
//    cout << endl;
//    bubble();
//    for (int i = 0; i < n; i++)
//    {
//        cout << num[i] << ' ';
//    }
//}

//#include<iostream>
//using namespace std;
//int n;
//const int N = 10100;
//int num[100100];
//int idx = 0;
//bool st[N];
//int e[N], ne[N], h[N];
//void add(int a, int b)
//{
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx++;
//}
//int dfs(int u)
//{
//    st[u] = true;
//    int sum = 1; int s = 0;
//
//
//}
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add(a, b);
//    }
//    dfs(1);
//    return 0;
//}

//#include<iostream>
//using namespace std;
//int main()
//{
//    int a = 0;
//    int& c = a;
//    int& x = a;
//    x = 10;
//    cout << c;
//
//    return 0;
//}

//#include<iostream>
//using namespace std;
//int main()
//{
//    int n;
//    int sum = 1;
//    int t = 0;
//    scanf("%d", &n);
//    for (int i = n; i >1; i--)
//    {
//        sum = 2*(sum+1);
//        //t += sum;
//    }
//    printf("%d", sum);
//    return 0;
//}

//#include<iostream>
//using namespace std;
//int& Cout(int x)
//{
//    static int n = x;
//    n++;
//    return n;
//}
//int main()
//{
//
//
//    int& t = Cout(10);
//    cout <<t<<' '; 
//    printf("\n");
//    cout << t;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//#include<assert.h>
//typedef struct list 
//{
//    int a[100010];
//    size_t size;
//    int& at(int pos)
//    {
//        assert(pos >= 0 && pos < 100010);
//        return a[pos];
//    }
//} list;
//int main()
//{
//    list s;
//    s.at(0) = 1;
//    s.at(0)++;
//    cout << s.a[0] << endl;
//
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int p;
//    int max = 0;
//    int x = (-10,10 >= 9);
//    printf("%d", x);
//    /////// 0                1//////
//    while (scanf("%d", &p),p>=0)
//    {
//        if (max < p)
//        {
//            max =p;
//        }
//    }
//    printf("%d", max);
//    return 0;
//}

//#include<stdio.h>
//#include<math.h>
//int num[1010];
////int n;
//int main()
//{
//    int n;
//    int k = 0;
//    printf("%d", n);
//    /*scanf("%d", &n);
//    while (n)
//    {
//        num[k] = n % 10;
//        k++;
//        n /= 10;
//    }
//    for (int i = 0; i<k; i++)
//    {
//        printf("%d ", num[i]);
//    }*/
//    return 0;
//}

//#include<stdio.h>
//typedef int long long;
//int main()
//{
//    long long a;
//    int b;
//    int t;
//    scanf("%lld %lld", &a, &b);
//    long c = a * b;
//    int y = a % b;
//    while (1)
//    {
//        if (a < b)
//        {
//            t = a;
//            a = b;
//            b = t;
//        }
//        if (a % b == 0)
//        {
//            printf("%lld ", b);
//            printf("%lld\n", c / b);
//            break;
//        }
//        else
//        {
//            int y = a % b;
//            a = b;
//            b = y;
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    char ch;
//    while (scanf("%c", &ch),ch != '@')
//    {
//        
//        if (ch >= 'A' && ch <= 'Z')
//        {
//            ch += 32;
//        }
//        if (ch == 'z')
//        {
//            ch = 'a';
//        }
//        else if (ch >= 'a' && ch <= 'y')
//        {
//            ch += 1;
//        }
//            printf("%c", ch);
//    }
//    return 0;
//}

//#include<stdio.h>
//int num[10010];
//int main()
//{
//    int n;
//    scanf("%d", &n);//这个二进制序列的长度
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &num[i]);//存储这个二进制序列
//    }
//    int s = 0;
//    for (int i = 0; i < n; i++)
//    {
//        s = s * 2 + num[i];//s是转换为十进制的数字
//    }
//    printf("%d", s);
//    return 0;
//}










//#include<stdio.h>
//struct ListNode {
//	int val;
//	struct ListNode* next;
//};
//struct ListNode* partition(struct ListNode* head, int x)
//{
//	if (head  == NULL || head->next == NULL)
//	{
//		return head;
//	}
//	struct ListNode* head1 = malloc(sizeof(struct ListNode));//小数的链表
//	struct ListNode* head2 = malloc(sizeof(struct ListNode));//大数的链表
//	struct ListNode* small = head1;
//	struct ListNode* big = head2;
//	struct ListNode* cur = head;
//	while (cur)
//	{
//		if (cur->val < x)
//		{
//			small->next = cur;
//			small = small->next;
//		}
//		else
//		{
//			big->next = cur;
//			big = big->next;
//		}
//		cur = cur->next;
//	}
//	//拼接俩个链表
//	head1->next = head2->next;
//	big->next = NULL;
//	head->next = NULL;
//	return head1->next;
//}
//int main()
//{
//
//
//
//	return 0;
//}





#include<stdio.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* partition(struct ListNode* head, int x)
{
	if (head  == NULL || head->next == NULL)
	{
		return head;
	}
	struct ListNode* head1 = malloc(sizeof(struct ListNode));//小数的链表
	struct ListNode* head2 = malloc(sizeof(struct ListNode));//大数的链表
	struct ListNode* small = head1;
	struct ListNode* big = head2;
	struct ListNode* cur = head;
	while (cur)
	{
		if (cur->val < x)
		{
			small->next = cur;
			small = small->next;
		}
		else
		{
			big->next = cur;
			big = big->next;
		}
		cur = cur->next;
	}
	//拼接俩个链表
	head1->next = head2->next;
	big->next = NULL;
	head->next = NULL;
	return head1->next;
}
int main()
{



	return 0;
}